package com.lcm.algorithm.datatest.array;

/**
 * @description: 215.数组中第k大的元素
 * @author: lcm
 * @create: 2020-04-02 16:44
 **/

public class FindKthLargest {

    public static void main(String[] args){
        int[] array=new int[]{3,2,1,5,6,4};
        System.out.println(findKthLargest(array,2));
    }

    /**
     * 1.暴力，排序，O(nlgn)
     * 2.小根堆，装入k个最大数字，如果有更大的，移出根节点，将这个数字放入小根堆 O(nlgk),因为k是常数，可以看作O(n)
     * 3.快速选择排序，其实就是优化后的快速排序算法，只需要执行快排的一部分，就能找到第k大的数，时间O(n)
     * @param nums
     * @param k
     * @return
     */
    public static int findKthLargest(int[] nums, int k){
        return help(nums,nums.length-k,0,nums.length-1);
    }

    static int help(int[] nums, int k,int from,int to){
        int index = position(nums,from,to);
        if(index==k){
            return nums[index];
        }else if(index>k){
            return help(nums,k,from,index-1);
        }else {
            return help(nums,k,index+1,to);
        }
    }

    static int position(int[] nums, int from,int to){
        //标兵值
        int n=nums[from];
        //
        int i=from,j=to;
        while (i<j){
            while(n<=nums[j]&&i<j){
                j--;
            }
            while (n>=nums[i]&&i<j){
                i++;
            }
            swap(nums,i,j);
        }
        swap(nums,from,i);
        return i;
    }

    static void swap(int[] nums,int i,int j){
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }
}
